home *** CD-ROM | disk | FTP | other *** search
/ QRZ! Ham Radio 8 / QRZ Ham Radio Callsign Database - Volume 8.iso / pc / files / p_misc / netconf.arc / NOCOLL.TXT < prev    next >
Text File  |  1988-12-10  |  18KB  |  393 lines

  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  
  8.  
  9.  
  10.                    A High Performance, Collision-Free Packet Radio
  11.                                        Network
  12.  
  13.  
  14.                                    Phil Karn, KA9Q
  15.  
  16.  
  17.  
  18.                                        _A_B_S_T_R_A_C_T
  19.  
  20.                      For the  past  several  years,  those  discussing
  21.                 "level 3 networking" have made much of the performance
  22.                 gains to be had through  hop-by-hop  acknowledgements.
  23.                 In  this paper I will show that, while sometimes help-
  24.                 ful, hop-by-hop ACKing is not the panacea it  is  gen-
  25.                 erally  perceived  to be.  Only fundamental changes in
  26.                 the way we allocate and use  frequencies  will  really
  27.                 fix the problem.
  28.  
  29.  
  30.  
  31.            _1.  _I_n_t_r_o_d_u_c_t_i_o_n
  32.  
  33.                 At  present,  our  networks  can  best  be   described   as
  34.            "anarchistic."   Single frequency digipeaters abound, and every-
  35.            one knows just how likely you are to get a  packet  across  five
  36.            digipeater  hops  on a heavily loaded frequency [2].  Given this
  37.            situation, software that  provides  hop-by-hop  acknowledgements
  38.            (e.g.,   NET/ROM   [4])   is  clearly  a  major  win.   Actively
  39.            retransmitting ACKs, as in the ACK-ACK protocol [3] would  yield
  40.            an additional improvement.
  41.  
  42.                 Yet NET/ROM and ACK-ACK both fail to attack the fundamental
  43.            problem:  _c_a_r_r_i_e_r  _s_e_n_s_e  _m_u_l_t_i_p_l_e  _a_c_c_e_s_s (_C_S_M_A) _s_i_m_p_l_y _d_o_e_s_n'_t
  44.            _w_o_r_k _v_e_r_y _w_e_l_l _o_n _a_n _o_p_e_n-_a_c_c_e_s_s  _s_i_m_p_l_e_x  _r_a_d_i_o  _c_h_a_n_n_e_l.   Two
  45.            things  contribute  to this.  The first is the well-known _h_i_d_d_e_n
  46.            _t_e_r_m_i_n_a_l _p_r_o_b_l_e_m: not sensing carrier on the  channel  does  NOT
  47.            guarantee that you won't interfere with someone if you transmit.
  48.  
  49.                 The second problem is less well known.  Because it  is  the
  50.            converse  of  the  hidden  terminal  problem  I will call it the
  51.            _e_x_p_o_s_e_d _t_e_r_m_i_n_a_l _p_r_o_b_l_e_m.[1] A station in a good location (e.g.,
  52.            a  mountaintop)  may  hear  local  traffic from within a distant
  53.            area.  Not knowing that it would not interfere with that traffic
  54.            by transmitting, it defers unnecessarily and wastes an opportun-
  55.            ity to reuse the frequency locally.
  56.            _________________________
  57.              [1] George Flammer,  WB6RAL,  calls  this  the  _w_h_i_t_e
  58.            _l_i_g_h_t_n_i_n_g effect. [1]
  59.  
  60.  
  61.  
  62.  
  63.                                    December 6, 1988
  64.  
  65.  
  66.  
  67.  
  68.  
  69.  
  70.  
  71.  
  72.                 In short, the carrier detect line from the modem  is  often
  73.            useless.   There  is  no guarantee that you won't interfere with
  74.            someone if you transmit when you don't hear a carrier, and  con-
  75.            versely  there  is  no  guarantee  that you _w_o_u_l_d interfere with
  76.            another transmission even if you transmit when  you  _d_o  hear  a
  77.            carrier.
  78.  
  79.                 It is well known (and proven in practice!) that CSMA breaks
  80.            down  in  the presence of hidden terminals, degrading rapidly to
  81.            the performance of pure Aloha (where stations transmit at  will,
  82.            without  first monitoring the channel).  With the standard Aloha
  83.            assumptions (many terminals each generating a tiny  fraction  of
  84.            the   total   channel   load)  the  maximum  attainable  channel
  85.            throughput is only 18%.  This occurs at an offered load of  50%,
  86.            i.e.,  each  packet has to be transmitted about 2.7 times on the
  87.            average for it to be received once.   Although  hop-by-hop  ack-
  88.            nowledgements  keep  these  figures  from  getting exponentially
  89.            worse across a multi-hop path, they do _n_o_t fix  the  fundamental
  90.            problem: _C_H_A_N_N_E_L _C_O_L_L_I_S_I_O_N_S!
  91.  
  92.                 This is a very important point.  _U_s_i_n_g _l_i_n_k _l_e_v_e_l  _A_C_K_s  _t_o
  93.            _i_m_p_r_o_v_e  _p_e_r_f_o_r_m_a_n_c_e  _i_s, _a_t _b_e_s_t, _a _b_a_n_d-_a_i_d _s_o_l_u_t_i_o_n.  Because
  94.            they represent overhead, sometimes they are actually counterpro-
  95.            ductive.   The  real challenge, therefore, is to make collisions
  96.            impossible in normal operation. I will now discuss  two  of  the
  97.            traditional  methods  for collision avoidance when hidden termi-
  98.            nals are present.
  99.  
  100.            _2.  _T_o_k_e_n _P_a_s_s_i_n_g
  101.  
  102.                 One way to avoid collisions is to require each  station  to
  103.            wait for explicit, one-at-a-time permission to transmit.  When a
  104.            station has sent its traffic, it passes this authority on to the
  105.            next  station.   Since  the  message  that  grants permission to
  106.            transmit is known as a _t_o_k_e_n, this  scheme  is  known  as  _t_o_k_e_n
  107.            _p_a_s_s_i_n_g.
  108.  
  109.                 Token passing works well in small  networks  with  reliable
  110.            nodes  and  links,  but it doesn't scale well.  Complex recovery
  111.            algorithms must be worked out to recover from lost tokens caused
  112.            either  by  failing  nodes  or transmission errors.  In a packet
  113.            radio network with many hidden terminals,  the  route  that  the
  114.            token  will  take  must  be  mapped out in advance; it cannot be
  115.            passed between stations that cannot  communicate.  This  compli-
  116.            cates the addition of new stations to the network.  In addition,
  117.            much time is wasted passing the token when there are  many  sta-
  118.            tions  in  the  network  but  only  a  few  are actually sending
  119.            traffic.  Nevertheless, token passing is a completely unexplored
  120.            technique in amateur radio, one that deserves serious considera-
  121.            tion for special circumstances.
  122.  
  123.  
  124.  
  125.  
  126.  
  127.                                    December 6, 1988
  128.  
  129.  
  130.  
  131.  
  132.  
  133.  
  134.  
  135.  
  136.            _3.  _B_u_s_y _T_o_n_e _M_u_l_t_i_p_l_e _A_c_c_e_s_s (_B_T_M_A)
  137.  
  138.                 Another effective technique for eliminating collisions when
  139.            hidden  terminals  are present is for each station to transmit a
  140.            signal on a separate frequency whenever it is actively receiving
  141.            a  packet.  If  another  node  hears  this  _b_u_s_y _t_o_n_e, it avoids
  142.            transmitting knowing that it would interfere with the  reception
  143.            in  progress.  It is not necessary for a node to couple its busy
  144.            tone directly to the receiver carrier detect indication; it  may
  145.            drop  the  busy  tone once it determines by examining the packet
  146.            destination address that the packet is for another station. This
  147.            allows  _f_r_e_q_u_e_n_c_y _r_e_u_s_e (successful simultaneous use of the same
  148.            frequency by two pairs of  stations  far  enough  apart  not  to
  149.            interfere with each other).
  150.  
  151.                 In theory, BTMA can be an effective solution to the  hidden
  152.            terminal  problem.   However,  extra  radio hardware is required
  153.            since the busy tone transmitter must operate without interfering
  154.            with  data reception. In practice this means using separate fre-
  155.            quency bands, and it may be difficult to get the  range  of  the
  156.            busy tone transmitter to match that of the data transmitter -- a
  157.            fundamental assumption in BTMA. It is also difficult to get BTMA
  158.            to  solve  the  exposed  terminal  problem.  Hearing a busy tone
  159.            doesn't _a_l_w_a_y_s mean that you'd interfere with a receiver if  its
  160.            desired  signal  is  much  stronger than yours, depending on the
  161.            capture ratio of the modulation method in use.  Setting the busy
  162.            tone's  amplitude  in  inverse  relationship to the level of the
  163.            signal being received, plus lots of tricky threshold adjustments
  164.            in the busy tone receivers, might make this work.
  165.  
  166.            _4.  _C_o_n_t_e_n_t_i_o_n-_F_r_e_e _C_h_a_n_n_e_l_s
  167.  
  168.                 The discussion so far has centered on reducing or eliminat-
  169.            ing  collisions  when  a single frequency must be shared by more
  170.            than one transmitter.  Contention channels are likely to be with
  171.            us  for  some time where random end-users are involved. However,
  172.            the emerging network of dedicated,  "backbone"  sites  need  not
  173.            follow  the  same  anarchistic  model.  The  rest  of this paper
  174.            discusses a more disciplined  approach  that  appears  extremely
  175.            attractive for such stations.
  176.  
  177.                 One sure way to eliminate collisions is  to  eliminate  all
  178.            but  one  transmitter on each frequency.  All other transmitters
  179.            on the same frequency must be placed far enough  apart  so  that
  180.            their  coverage  areas  do  not  overlap.   Each  station uses a
  181.            separate, dedicated receiver to hear each of its  neighbors;  it
  182.            does  not  listen on its own transmit frequency.  A network node
  183.            might look like this:
  184.  
  185.  
  186.  
  187.                       Beam or Omni   Beam or Omni   Beam or Omni
  188.                         Antenna        Antenna        Antenna
  189.  
  190.  
  191.  
  192.                                    December 6, 1988
  193.  
  194.  
  195.  
  196.  
  197.  
  198.  
  199.  
  200.  
  201.                        Receiver 1     Receiver 2     Receiver N
  202.  
  203.                      ___________________________________________
  204.                     |               Packet switch              |
  205.                      ___________________________________________
  206.  
  207.                                      Transmitter
  208.  
  209.                                      Omni antenna
  210.  
  211.  
  212.                 Many things now become easier or perhaps even possible  for
  213.            the  first  time.   As it is no longer necessary to "get off the
  214.            frequency" quickly when a station has  sent  its  traffic,  fast
  215.            transmit-receive  switching is no longer required.  Transmitters
  216.            and power amplifiers with  relays  or  slow-lockup  synthesizers
  217.            need not be modified; they could operate either continuously, or
  218.            with tail timers like those  in  conventional  voice  repeaters.
  219.            Similarly,  coherent receiver demodulators (which work well with
  220.            very low signal levels but require relatively  long  acquisition
  221.            times)   need   not  penalize  network  performance.   The  link
  222.            receivers may be cheap  pocket  scanners  since  they  need  not
  223.            transmit.   If  adjacent  nodes transmit on different bands, the
  224.            expense of repeater-style duplexers  can  be  avoided,  although
  225.            filter cavities ("trashcans") may still be needed (especially at
  226.            hilltop sites) to reject strong out-of-band signals.
  227.  
  228.                 Since the design of this network makes collisions  impossi-
  229.            ble,  with  proper modem design and adequate RF link margins the
  230.            raw packet loss rate should be very low.   The  occasional  end-
  231.            to-end  retransmission  of  a  dropped  packet will be more than
  232.            offset by the savings in overhead gained by avoiding link  level
  233.            acknowledgements.  High channel speeds are much easier to handle
  234.            since the packet switches are much simpler, and real time appli-
  235.            cations  such  as packet voice become practical. Since the nodes
  236.            are inherently full duplex, sliding-window  transport  protocols
  237.            (with  data  packets and acknowledgements flowing simultaneously
  238.            in both directions) finally make sense, as  data/ack  collisions
  239.            are avoided.
  240.  
  241.  
  242.            _5.  _B_r_o_a_d_c_a_s_t_i_n_g
  243.  
  244.                 In addition, some very powerful broadcast techniques become
  245.            possible.   Much  of  the traffic now handled by bulletin boards
  246.            consists of undirected messages read by  a  wide  audience.   At
  247.            present,  our  virtual circuit protocols require that a separate
  248.            copy be sent to and acknowledged  by  every  interested  reader.
  249.            This  wastes  one  of  the  most useful and unique properties of
  250.            radio: the ability of more than one receiver to  hear  a  single
  251.            transmitter.   Efficient  but  reliable  broadcasting  on a very
  252.            unreliable channel (e.g., an  existing  digipeater  network)  is
  253.            almost impossible.  However, the situation changes completely if
  254.            the raw packet loss rate can be lowered to a reasonable level.
  255.  
  256.  
  257.                                    December 6, 1988
  258.  
  259.  
  260.  
  261.  
  262.  
  263.  
  264.  
  265.  
  266.                 Consider the operation of an ordinary voice  bulletin  net,
  267.            one  organized to disseminate information of general interest to
  268.            many stations. (A good example is the Tuesday night AMSAT net on
  269.            75  meters).   After  the  control  station finishes reading, he
  270.            invites requests for repeats.  If conditions are  good,  only  a
  271.            few  stations  will respond, and the requested message fragments
  272.            are retransmitted.   As  with  the  original  transmission,  all
  273.            receiving  stations  are  free  to make use of the retransmitted
  274.            information; this often preempts a second station's request  for
  275.            a  fill.   If  conditions are bad, the control station may first
  276.            read the entire bulletin several times (a simple form of forward
  277.            error correction) to cut down the number of fill requests.
  278.  
  279.            _6.  _F_l_o_o_d _R_o_u_t_i_n_g
  280.  
  281.                 Given a reasonably reliable channel (i.e., one with only  a
  282.            single  transmitter)  this  scheme  should  be easy to automate.
  283.            Wide-area bulletin coverage could be achieved with a flood rout-
  284.            ing  scheme  similar  to  the USENET bulletin board network.  In
  285.            flooding, a node originating a message transmits it  to  all  of
  286.            its  neighbors.   Each  message  contains  a unique network-wide
  287.            identifier (e.g., the node address concatenated  with  a  serial
  288.            number).   Each  receiving  node maintains a list of messages it
  289.            has already seen and ignores duplicates.  A  non-duplicate  mes-
  290.            sage is entered into the list and retransmitted to its neighbors
  291.            until it has spread to every reachable node in the network.
  292.  
  293.                 Flooding is extremely robust, as it  tries  every  possible
  294.            route to each node in parallel.  USENET has proven this in prac-
  295.            tice, despite an amazingly anarchistic network management style.
  296.            It  is the preferred way to reach large numbers of people, since
  297.            a given message crosses each link in the network  exactly  once.
  298.            Because  of  its  reliability, flooding is a useful fallback for
  299.            high  priority  point-to-point  traffic  when  ordinary  routing
  300.            schemes have failed.  (One often finds person-to-person messages
  301.            posted on USENET because  direct  mail  routing  hasn't  worked.
  302.            Clearly  this  is  to  be  discouraged  except  as a last resort
  303.            because of the unnecessary load this generates.)
  304.  
  305.            _7.  _S_u_m_m_a_r_y
  306.  
  307.                 The use of contention-based channel  access  algorithms  is
  308.            perhaps  unavoidable where end users are involved. However, such
  309.            free-for-alls are inappropriate on backbone links  in  light  of
  310.            the severe performance problems involved.  The evolving backbone
  311.            networks should take a more enlightened  approach.   Instead  of
  312.            just  attempting  to patch things up at a higher layer by adding
  313.            hop-by-hop acknowledgements, they should be carefully planned to
  314.            avoid collisions altogether.  Not only can the extra overhead of
  315.            hop-by-hop acknowledgements be avoided,  but  qualitatively  new
  316.            and vastly more efficient bulletin dissemination techniques fall
  317.            out almost for free.  Considering the  vastly  improved  perfor-
  318.            mance  and  functionality  that would result, the extra costs of
  319.            doing so are minimal.
  320.  
  321.  
  322.                                    December 6, 1988
  323.  
  324.  
  325.  
  326.  
  327.  
  328.  
  329.  
  330.  
  331.            _8.  _R_e_f_e_r_e_n_c_e_s
  332.  
  333.  
  334.            1.   Flammer,  G.,  "Survival  Training  for  Mountaintop  Digi-
  335.                 peaters," 73 Magazine, August 1986 p. 68.
  336.  
  337.            2.   Clark, T., "The Trouble with Digipeaters," Gateway.
  338.  
  339.            3.   Karn, P. and Lloyd, B.: "Link Level  Protocols  Revisited,"
  340.                 ARRL  Amateur  Radio  Fifth Computer Networking Conference,
  341.                 pp. 5.25-5.37, Orlando, 9 March 1986.
  342.  
  343.            4.   Raikes, R., and Busch, M., "NET/ROM  Version  1  Documenta-
  344.                 tion," Software 2000 Inc, May, 1987.
  345.  
  346.  
  347.  
  348.  
  349.  
  350.  
  351.  
  352.  
  353.  
  354.  
  355.  
  356.  
  357.  
  358.  
  359.  
  360.  
  361.  
  362.  
  363.  
  364.  
  365.  
  366.  
  367.  
  368.  
  369.  
  370.  
  371.  
  372.  
  373.  
  374.  
  375.  
  376.  
  377.  
  378.  
  379.  
  380.  
  381.  
  382.  
  383.  
  384.  
  385.  
  386.                                    December 6, 1988
  387.  
  388.  
  389. 
  390.